package com.Jancode.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class MinCostToConnectAllPoints {
    class Solution {
        private static final int DISTANCE_MAX_VALUE = Integer.MAX_VALUE;
        private PriorityQueue<Integer> pq;   // the crossing edges
        private int[] distTo;                // distTo[v] = the shorest cost from the non-tree vertices to tree vertices 
        private boolean[] marked;            // marked[v] = v is in the MST 
        private List<Edge> edges;            // the edges for this problem
        private int costs;

        public int minCostConnectPoints(int[][] points) {
            int V = points.length;         // the numbers of vertices
            // init 
            marked = new boolean[V];
            distTo = new int[V];
            pq = new PriorityQueue<>((v, w) -> distTo[v] - distTo[w]);
            edges = new LinkedList<>();

            for(int i = 0; i < V; i++) {
                for(int j = i + 1; j < V; j++) {
                    edges.add(new Edge(i, j, dist(points, i, j)));
                }
                distTo[i] = DISTANCE_MAX_VALUE;
            }

            prim(0);

            for(int dist : distTo) {
                costs += dist;
            }

            return costs;
        }

        private void prim(int s) {
            distTo[s] = 0;

            pq.offer(s);
            while(!pq.isEmpty()) {
                int v = pq.poll();

                marked[v] = true;
                for(Edge edge : edges) {
                    if(edge.contains(v)) {
                        int w = edge.other(v);
                        if(marked[w]) continue;

                        if(edge.weight < distTo[w]) {
                            distTo[w] = edge.weight;
                            pq.offer(w);
                        }
                    }
                }
            }
        }

        private int dist(int[][] points, int v, int w) {
            int distance = 0;

            distance += Math.abs(points[v][0] - points[w][0]);  // |x_i - x_j|
            distance += Math.abs(points[v][1] - points[w][1]);  // |y_i - y_j|

            return distance;
        }

        private class Edge implements Comparable<Edge>{
            int v;
            int w;
            int weight;

            public int either() {
                return v;
            }

            public int other(int o) {
                if(o == v) return w;
                if(o == w) return v;
                throw new NoSuchElementException();
            }

            public boolean contains(int v) {
                if(this.v == v || this.w == v) return true;
                
                return false;
            }

            public Edge(int v, int w, int weight) {
                this.v = v;
                this.w = w;
                this.weight = weight;
            }

            @Override
            public int compareTo(Edge that) {
                return Integer.compare(this.weight, that.weight);
            }
        }
    }

    public static void main(String[] args) {
        int[][] points = {{0,0},{2,2},{3,10},{5,2},{7,0}};

        int costs = new MinCostToConnectAllPoints().new Solution().minCostConnectPoints(points);

        System.out.println(costs);
    }
}